#define _CRT_SECURE_NO_WARNINGS
#include<vector>
#include<string>
#include<unordered_set>
using namespace std;
bool wordBreak(string s, vector<string>& wordDict) {
    int n = s.size();
    unordered_set<string> mp(wordDict.begin(), wordDict.end());
    vector<bool> dp(n + 1);
    dp[0] = true;
    s = '_' + s;
    for (int i = 1; i <= n; i++) {
        int j = i;
        for (; j >= 1; j--) {
            string str(s.begin() + j, s.begin() + i + 1);
            if (mp.count(str) > 0&&dp[j-1]==true) {
                dp[i] = true;
                break;
            }
        }
        if (j == 0)dp[i] = false;
    }
    return dp[n];
}
int main() {
    string s("catsandog");
    vector<string> v = { "cats", "dog", "sand", "and", "cat" };
    wordBreak(s,v);
    return 0;
}